The present invention relates to hash tables. In particular, the present invention relates to the efficient implementation of a hash table in a multi-process environment.
A hash table consists of a set of buckets that are addressed by applying a hashing function to a data key associated with data to be stored or retrieved from a hash table. Because of limited resources, a hash table typically only has a finite number of buckets into which the data keys may be assigned. As a result, it is possible that more than one data key may be assigned to the same bucket in the hash table.
To deal with such collisions of data keys, it is common to use a method known as chaining in which the hash function indexes a pointer to a linked list of nodes, where each node contains a key and the data associated with the key. Because it is a linked list, each node also includes a pointer to the next node in the linked list.
In such systems, data is added to the hash table by first applying a hash function to the data's key. This hash function generates a hash signature, which may be used directly to address the individual buckets within the hash table. However, to ensure that each hash signature is associated with a bucket within the finite space of the hash table, it is common to apply a modulo N function to the hash signature where N is the number of buckets in the hash table. Once the bucket has been identified, a new node is inserted into the bucket's linked list and the node is populated with the data and key.
To look up data in a hash table, the key for the data is applied to the hash function to identify the bucket that contains the data. The keys in each node of the linked list associated with that bucket are then compared to the search key. A pointer to the node that contains the matching key is returned if a matching key is found.
To delete data from the hash table, the key is first used to find the data as described above. The node is then removed from the linked list.
In multi-process or multi-threaded environments, it is possible for many different processes or threads to want to access or change a hash table. To avoid corruption of the hash table, early systems locked the entire hash table or individual nodes in the hash table when a process was using the table or the entry. This prevented parallel processes from taking actions on the table that were incompatible with each other and that would lead to corruption of the data. For example, by locking the table, it was possible to prevent two processes from separately adding different nodes for a same data key.
Locking the entire hash table or a node in the hash table is undesirable since it forces one process to wait while another process is using the hash table. To overcome this problem, lock-free hash tables have been developed. However, the lock-free implementations have had several deficiencies.
For example, during traversal of the linked list, many systems require a large number of computationally expensive memory operations. For example, in one system, synchronous memory writes are used during traversal of the linked list. Such memory writes force the processor to update a memory location immediately instead of allowing the processor to fill a local memory buffer before updating the memory when it is most efficient for the processor. In other systems, interlocked operations are used in which a value stored in memory is compared to an expected value and is replaced with a new value if the stored value matches the expected value. If the stored value does not match, the stored value is not changed and is returned. Examples of such interlocked operations include compare-and-swap (CAS) and Interlocked Compare and Exchange (ICE). Other systems rely on very complicated data structures that require overly complex algorithms for their management.
Using such computationally intensive instructions at each traversal of a node along a linked list makes traversal computationally expensive. Since every option performed on a hash table involves a traversal, using such instructions for each traversal slows the operation of the hash table.
Some lock-free implementations have been developed that rely on special hardware support, for example special micro-processors that support unique processor instructions or precision timers that are perfectly synchronized across all central processing units. Reliance on such specialized hardware is undesirable because it limits the environments in which the hash tables may be executed.
Other lock-free implementations have been developed that do not lock the table but that allow different threads to block each other. Such systems are subject to live-lock conditions in which two threads try to accomplish an operation on a same hash node and as a result block the progress of each other indefinitely.
In addition, lock-free hash tables of the past have not had an efficient means for managing memory. Typically, in order to reduce the amount of memory used by the hash table, nodes are treated as independent objects that can be inserted into any linked list in the hash table and that may be reused after being removed from the linked list and marked as destroyed.
However, an object cannot be marked as destroyed until all of the applications or processes are done using the object. Thus, there must be some way to determine when a node is no longer being used so that it can be destroyed.
Some lock-free hash tables of the prior art have relied on system-based garbage collection for deleting unused nodes. In such garbage collection schemes, a system process that is separate from the hash table determines what objects are currently being used by running applications. Objects that are not being used by any of the applications are then destroyed. These systems are less than ideal because they require that the hash table be implemented in a particular computing environment and thus limit the portability of the hash table.
In other systems, a special memory management protocol is added to every application so that each application provides a list of all of the objects it is currently using. When an application is done using an object, it checks with every other application to see if it can delete the object. When another application is using the object, the deletion is postponed until that application is no longer using the object. This creates a possibly infinite delay in deleting objects that is undesirable. It also requires every application to be written in this manner.
Outside of the area of multi-process linked lists, reference counters have been used to determine when an object may be destroyed. In such systems, a counter in the object is incremented each time an application is given a pointer to the object and is decremented each time an application releases the pointer. If the reference counter reaches 0, the object may be destroyed.
Although such reference counters have been used outside of linked lists, it is difficult to use such reference counters in a multi-process environment in which the objects are nodes in a linked list. The reason for this is that the node's position in the linked list is physically and semantically separate from the reference count of the node. Thus, to delete a node, the node must be removed from the linked list and then the reference count must be examined to determine if the node can be destroyed. Since this requires two operations, it is possible that two separate processes can interfere with each other if the information is not synchronized.